rtk 2001

2001.1.1

Tipkanje

1. podnaloga

Predpostavimo, da lahko vse znake, ki jih želimo natipkati, razdelimo v dve skupini: nekatere tipkamo vedno z levo roko, druge pa vedno z desno.

Naloga

Napisana je funkcija dolzina_najdaljsega_podniza(vhod). Dopolni jo na mestih, označenimi z ###, da bo iz danega niza izračunala in vrnila dolžino takega najdaljšega podniza, ki ga je mogoče v celoti natipkati z eno samo roko.

def dolzina_najdaljsega_podniza(vhod):
   """Izračuna dolžino najdaljšega podniza v vhodnem nizu."""
    trenutna_roka = None
    max_z_eno = 0
    st_s_trenutno = 0
    ze_tipkamo = False  # Če smo pri prvem znaku, moramo znak obravnavati posebej.
    for crka in vhod:
        nova_roka = ###
        if not ze_tipkamo:
            ze_tipkamo = ###
            st_s_trenutno = 1
        elif nova_roka == trenutna_roka:
            # Z isto toko kot doslej natipkamo še en znak več.
            st_s_trenutno += 1
        elif st_s_trenutno > ###:
            # Zamenjamo roko. Mogoče smo z dosedanjo dosegli nov rekord.
            max_z_eno = st_s_trenutno
            st_s_trenutno = 1
        else:
            ###
        trenutna_roka = nova_roka
       ###

Na voljo imaš funkcijo s_katero_roko(crka), ki zna za vsak znak povedati, v katero od navedenih dveh skupin spada. Če ga napišemo z levo, nam vrne niz 'leva', sicer pa niz 'desna'.

Vhodni podatki

Niz, sestavljen iz črk, ki jih najdemo na slovenski tipkovnici.

Izhodni podatki

Dolžina najdaljšega podniza danega niza, ki ga je mogoče natipkati z eno samo roko.

Primer

Če se a in e tipkata vedno z levo roko, i, o in u pa vedno z desno, je pri nizu aeiou pravilni odgovor:

  >>> dolzina_najdaljsega_podniza('aeiou')
  3

Podniz iou lahko namreč natipkamo z desno roko. Poglejmo si še nekaj primerov.

  >>> dolzina_najdaljsega_podniza('aaeaiaoaua')
  4

Podniz aaea lahko namreč natipkamo z levo roko.

  >>> dolzina_najdaljsega_podniza('ouaeauo')
  3

Podniz aea lahko namreč natipkamo z levo roko.

  >>> dolzina_najdaljsega_podniza('uaoei')
  1

Nobenih dveh zaporednih znakov ne moremo natipkati z isto roko.

  >>> dolzina_najdaljsega_podniza('iieeoo')
  2

V tem primeru lahko niz ii v celoti natipkamo z desno ali pa ee z levo ali pa oo z desno.

Uradna rešitev

def s_katero_roko(crka):
    """Vrne niz, ki pove, s katero roko natipkamo dano črko."""
    leva = 'qwertasdfgyxcvbQWERTASDFGYXCVB'
    desna = 'zuiopšđhjklčćžnmZUIOPŠĐHJKLČĆŽNM'
    assert crka in leva or crka in desna
    if crka in leva:
        return 'leva'
    else:
        return 'desna'

def dolzina_najdaljsega_podniza(vhod):
    """Izračuna dolžino najdaljšega podniza v vhodnem nizu."""
    trenutna_roka = None
    max_z_eno = 0
    st_s_trenutno = 0
    ze_tipkamo = False  # Če smo pri prvem znaku, moramo znak obravnavati posebej.
    for crka in vhod:
        nova_roka = s_katero_roko(crka)
        if not ze_tipkamo:
            ze_tipkamo = True
            st_s_trenutno = 1
        elif nova_roka == trenutna_roka:
            # Z isto toko kot doslej natipkamo še en znak več.
            st_s_trenutno += 1
        elif st_s_trenutno > max_z_eno:
            # Zamenjamo roko. Mogoče smo z dosedanjo dosegli nov rekord.
            max_z_eno = st_s_trenutno
            st_s_trenutno = 1
        else:
            st_s_trenutno = 1
        trenutna_roka = nova_roka

    # Morda je redordno zaporedje tisto na koncu niza, zato vrnemo maksimum.
    return max(max_z_eno, st_s_trenutno)

2001.1.3

Besedilo v stolpcu

1. podnaloga

Imamo poljubno dolgo besedilo v neproporcionalni pisavi (vsi znaki so enako široki). Med besedami je zaradi poravnavanja desnega roba besedila včasih lahko po več kot en presledek. Nobena vrstica ni daljša od $90$ znakov.

Naloga

Na mestih, označenimi z ###, dopolni funkcijo stetje_stavkov(besedilo), da bo iz vhodne datoteke brala vrstice in preštela vse stavke, ki ustrezajo pogoju, da je celoten stavek napisan v eni vrstici. Predpostaviš lahko, da se besedilo konča s prazno vrstico.

def stetje_stavkov(besedilo):
    stanje = 'med'
    # Lahko se nahajamo v treh možnih stanjih: v praznem prostoru med dvema stavkoma ('med'),
    # lahko smo v stavku, ki se je začel v trenutni vrstici ('zacTren'),
    # ali pa v stavku, ki se je začel že v neki prejšnji vrstici ('zacPrej').
    # Možna stanja so torej 'zacTren', 'zacPrej', 'med'.
    n = ###

    with open(besedilo, 'r') as besedilo:
        for vrstica in besedilo:
            if stanje == 'zacTren':
                ###
            l = len(vrstica)
            for i in range(0, l):
                if stanje == 'med' and (vrstica[i] == ' '):
                    stanje = 'zacTren'
                if (vrstica[i] in ###) and ((i == l - 1) or vrstica[i + 1] in ' \n'):
                    if stanje == 'zacTren':
                        n += 1
                    stanje = 'med'
    return n

Opomba

Prvi stavek se začne s prvim znakom v besedilu. Vsak naslednji stavek se prične za znakom za konec stavka (to je lahko pika, klicaj ali vprašaj), ki mu sledi presledek ali konec vrstice (Zaradi enostavnosti zanemarimo primer, ko piki sledi narekovaj na koncu dobesednega navedka, kar v resnici tudi pomeni konec stavka, čeprav prejšnja definicija trdi drugače. Če bi se hoteli ukvarjati s takšnimi podrobnostmi, bi tako ali tako prišli v težave pri parih ?" in !", ki lahko pomenita konec stavka ali pa tudi ne.).

V besedilu ni okrajšav, kjer bi bila uporabljena pika (vsaka pika, ki ji sledi presledek ali konec vrstice, pomeni konec stavka).

Vhodni podatki

Datoteka .txt z besedilom.

Izhodni podatki

Število stavkov, ki so v celotni napisani v eni izmed vrstic.

Primer

V spodnjem besedilu je osem stavkov, ki so v celoti na eni sami vrstici.

"In God’s name what does this mean?" Harker cried out. "Dr
Seward, Dr Van Helsing, what is it? What has happened? What
is wrong? Mina, dear what is it? What does that blood mean?
My God, my God! Has it come to this!" And, raising himself
to his knees, he beat his hands wildly together. "Good God
help us! Help her! Oh, help her!"
With a quick movement he jumped from bed, and began to
pull on his clothes, all the man in him awake at the need
for instant exertion. "What has happened? Tell me all about
it!" he cried without pausing. "Dr Van Helsing, you love
Mina, I know. Oh, do something to save her. It cannot have
gone too far yet. Guard her while I look for him!"

Uradna rešitev

def stetje_stavkov(besedilo):
    """Pregleda dano besedilo in prešteje stavke, ki so v celoti zapisani v eni
    vrstici. Vrne število takih stavkov."""

    stanje = 'med'
    # Lahko se nahajamo v treh možnih stanjih: v praznem prostoru med dvema stavkoma ('med'),
    # lahko smo v stavku, ki se je začel v trenutni vrstici ('zacTren'),
    # ali pa v stavku, ki se je začel že v neki prejšnji vrstici ('zacPrej').
    # Možna stanja so torej 'zacTren', 'zacPrej', 'med'.

    n = 0

    with open(besedilo, 'r') as besedilo:
        for vrstica in besedilo:
            if stanje == 'zacTren':
                stanje = 'zacPrej'
            l = len(vrstica)
            for i in range(0, l):
                if stanje == 'med' and (vrstica[i] == ' '):
                    stanje = 'zacTren'
                if (vrstica[i] in '.!?') and ((i == l - 1) or vrstica[i + 1] in ' \n'):
                    if stanje == 'zacTren':
                        n += 1
                    stanje = 'med'
    return n

2001.1.4

Pitagorejske trojice

1. podnaloga

Naloga

Dopolni funkcijo stevilo_trojic(a, b) na mestih, ki so označena z ###, da bo za dani celi števili $a$ in $b$ ($a$ je manjše ali enako $b$, obe števili pa sta večji ali enaki $1$) ugotovila, koliko je trojic pozitivnih celih števil $(x, y, z)$, za katere je $x^2 + y^2 = z^2$ in je $z$ med $a$ in $b$, lahko je kateremu od njiju tudi enak.

###
def stevilo_trojic(a, b):
    n = 0
    ###
    while z <= b:
        x = 1
        while x < z:
            y = math.sqrt(z * z - x * x)
            if y.is_integer():
                n += 1
            x += 1
        ###
    return n

Vhodni podatki

Dve naravni števili.

Izhodni podatki

Število pitagorejskih trojic, ki ustrezajo pogojem.

Primer

>>> stevilo_trojic(5, 20)
12

Za $a = 5$ in $b = 20$ funkcija vrne število $12$, saj obstaja dvanajst trojic števil, ki ustrezajo zgoraj opisanim pogojem. To so:

$(3, 4, 5)$, $(4, 3, 5)$, $(6, 8, 10)$, $(8, 6, 10)$, $(5, 12, 13)$, $(12, 5, 13)$, $(9, 12, 15)$, $(12, 9, 15)$, $(8, 15, 17)$, $(15, 8, 17)$, $(12, 16, 20)$, $(16, 12, 20)$.

Uradna rešitev

import math
def stevilo_trojic(a, b):
    """Izračuna število pitagorejskih trojic (x, y, z), za katere velja, da je
    z med vključno a in b."""
    n = 0
    z = a
    while z <= b:
        x = 1
        while x < z:
            y = math.sqrt(z * z - x * x)
            if y.is_integer():
                n += 1
            x += 1
        z += 1
    return n